{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# 3.5 The Concept of Memory\n", "\n", "[These sections are based on your textbook, [Introduction to Computing Systems: From Bits & Gates to C & Beyond (second edition)](http://highered.mheducation.com/sites/0072467509/index.html), by Yale N. Patt & Sanjay J. Patel, McGraw Hill Publishers, 2004.]\n", "\n", "We now describe one of the most important structures in the electronic digital computer, its memory. We explore how memory fits into the basic scheme of computer processing, and you will see throughout the rest of the book and indeed the rest of your work with computers how important the concept of memory is to computing.\n", "\n", "Memory is made up of a (usually large) number of locations, each uniquely identifiable and each having the ability to store a value. We refer to the unique identifier associated with each memory location as its *address*. We refer to the number of bits of information stored in each location as its *addressability*. For example, an advertisement for a personal computer might say, \"This computer comes with 16 megabytes of memory.\" Actually, most ads generally use the abbreviation 16 MB. This statement means, as we will explain momentarily, that the computer system includes 16 million memory locations, each containing 1 byte of information. \n", "\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 3.5.1 Address Space\n", "\n", "We refer to the total number of uniquely identifiable locations as the memory's *address space*. A 16 MB memory, for example, refers to a memory that consists of 16 million uniquely identifiable memory locations. \n", "\n", "Actually, the number *16 million* is only an approximation, due to the way we identify memory locations. Since everything else in the computer is represented by sequences of Os and 1 s, it should not be surprising that memory locations are identified by binary addresses as well. With n bits of address, we can uniquely identify 2n locations. Ten bits provide 1,024 locations, which is approximately 1,000. If we have 20 bits to represent each address, we have 220 uniquely identifiable locations, which is approximately 1 million. Thus 16 mega really corresponds to the number of uniquely identifiable locations that can be specified with 24 address\n", "bits. We say the address space is 224, which is exactly 16,777,216 locations, rather than 16,000,000, although we colloquially refer to it as 16 million." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 3.5.2 Addressability\n", "\n", "The number of bits stored in each memory location is the memory's *addressability*.\n", "A 16 megabyte memory is a memory consisting of 16,777,216 memory\n", "locations, each containing 1 byte (i.e., 8 bits) of storage. Most memories are byte-addressable.\n", "The reason is historical; most computers got their start processing\n", "data, and one character stroke on the keyboard corresponds to one 8-bit ASCII\n", "character, as we learned in Chapter 2. If the memory is byte-addressable, then each\n", "ASCII code occupies one location in memory. Uniquely identifying each byte of\n", "memory allowed individual bytes of stored information to be changed easily.\n", "\n", "Many computers that have been designed specifically to perform large scientific\n", "calculations are 64-bit addressable. This is due to the fact that numbers used\n", "in scientific calculations are often represented as 64-bit floating point quantities.\n", "Recall that we discussed the floating point data type in Chapter 2. Since scientific\n", "calculations are likely to use numbers that require 64 bits to represent them, it is\n", "reasonable to design a memory for such a computer that stores one such number\n", "in each uniquely identifiable memory location. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# 5.1 The ISA: Overview\n", "\n", "The ISA specifies all the information about the computer that the software has to\n", "be aware of. In other words, the ISA specifies everything in the computer that is\n", "available to a programmer when he/she writes programs in the computer's own\n", "machine language. Thus, the ISA also specifies everything in the computer that \n", "is available to someone who wishes to translate programs written in a high-level\n", "language like C or Pascal or Fortran or COBOL into the machine language of the\n", "computer.\n", "\n", "The ISA specifies the memory organization, register set, and instruction set,\n", "including opcodes, data types, and addressing modes.\n", "\n", "**NOTE**: Languages like Python and Java have their own, higher-level virtual machine instruction set. This allows the lower-level language (often written in C) to be easily ported from one instruction set to another." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 5.1.1 Memory Organization\n", "\n", "The LC-3 memory has an address space of 216 (i.e., 65,536) locations, and an\n", "addressability of 16 bits. Not all 65,536 addresses are actually used for memory\n", "locations, but we will leave that discussion for Chapter 8. Since the normal unit\n", "of data that is processed in the LC-3 is 16 bits, we refer to 16 bits as one word,\n", "and we say the LC-3 is word-addressable." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Cycles\n", "\n", "[Based on information in Chapter 4.]\n", "\n", "As we will see, **THE CONTROL UNIT** consists of all the structures needed to manage\n", "the processing that is carried out by the computer. Its most important\n", "structure is the **Finite State Machine** (FSM), which directs all the activity. \n", "Processing is carried out step by step, or rather, clock cycle by clock cycle. \n", "\n", "## The Clock\n", "\n", "[Based on information in Chapter 3.]\n", "\n", "Frequently, the mechanism that triggers the transition from one state to the\n", "next is a clock circuit. A clock circuit, or, more commonly, a clock, is a signal\n", "whose value alternates between 0 volts and some specified fixed voltage. In digital\n", "logic terms, a clock is a signal whose value alternates between 0 and 1.\n", "\n", "\n", "\n", "The clock is used to synchronized all of the electronics in the computer circuitry. As we shall see, a FSM has a series of states that it progresses through to perform different functions. Two such functions are:\n", "\n", "1. retrieving information from a register (1 cycle)\n", "2. retrieving information from a memory location (many cycles, depending on instruction)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 5.1.2 Registers\n", "\n", "Since it usually takes far more than one machine cycle to obtain data from memory,\n", "the LC-3 provides (like almost all computers) additional temporary storage\n", "locations that can be accessed in a single machine cycle.\n", "\n", "The most common type of temporary storage locations and the one used in\n", "the LC-3 is the general purpose register set. Each register in the set is called a\n", "general purpose register (GPR). Registers have the same property as memory\n", "locations in that they are used to store information that can be retrieved later. The\n", "number of bits stored in each register is usually one word. In the LC-3, this means\n", "16 bits.\n", "\n", "Registers must be uniquely identifiable. The LC-3 specifies eight GPRs, each\n", "identified by a 3-bit register number. They are referred to as RO, R1, R2, R3, R4, R5, R6, and R7." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Instruction Variations\n", "\n", "So far, we have seen the following instructions:\n", "\n", "1. ADD - 0001 DST SRC 1 VVVVV\n", "2. HALT - 1111 0000 00100101\n", "3. AND - 0101 DST SRC 1 VVVVV\n", "4. NOT - 1001 DST SRC 111111\n", "\n", "We will refer to each of the bits of an instruction by the numbering from right to left, like this:\n", "\n", "```\n", "15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0\n", "```\n", "\n", "surrounded by brackets. So, [0] is the right-most bit, and [15] is the left-most bit.\n", "\n", "A range of bits will be referred to using [LEFT:RIGHT]. So, [3:0] is the 4 right-most bits, and [15:12] is the left-most bits (e.g., the instruction).\n", "\n", "ADD and AND operate on the contents of registers and an *immediate value* VVVVV. Recall that the value VVVVV is sign-extended before any operation. So that:\n", "\n", "```\n", "01111\n", "```\n", "\n", "will be sign-extended to be these 16 bits:\n", "\n", "```\n", "0000000000001111\n", "```\n", "\n", "Likewise:\n", "\n", "```\n", "10000\n", "```\n", "\n", "will be sign-extended to be these 16 bits:\n", "\n", "```\n", "1111111111110000\n", "```\n", "\n", "However, AND and ADD can also operate on the contents of a register by using the 0 (non-immediate) flag:\n", "\n", "1. ADD - 0001 DST SRC 0 00 SRC\n", "2. AND - 0101 DST SRC 0 00 SRC\n", "\n", "The second SRC operand for both ADD and AND instructions can be specified\n", "by either register mode (0) or as an immediate operand (1). Bit [5] determines which\n", "is used. If bit [5] is 0, then the second source operand uses a register, and bits\n", "[2:0] specify which register. In that case, bits [4:3] are set to 0 to complete the\n", "specification of the instruction.\n", "\n", "In these versions of the instructions, we change the 1 flag to a 0, and change VVVVV to 00SRC. This SRC will use the contents of the SRC register. So the instruction:\n", "\n", "```\n", "0001 001 010 0 00 011\n", "```\n", "\n", "will use the contents of register 011 (R3) and ADD that to the contents of register 010 (R2) and store the results in register 001 (R1).\n", "\n", "Let's try out these instructions:\n", "\n", "ADD the contents of R0 + R0 and store to R1:" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " PC <= x3000\n", " memory[x3000] <= x1200\n", " PC <= x3001\n", " memory[x3001] <= xF025\n", " PC <= x3002\n", "Assembled! Use %dis or %dump to examine; use %exe to run.\n" ] } ], "source": [ ".ORIG x3000\n", "\n", "0001 001 000 0 00 000 ;; ADD R1 <= R0 + R0\n", "1111 0000 00100101 ;; \n", "\n", ".END" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "============================================================\n", "Computation completed\n", "============================================================\n", "Instructions: 2\n", "Cycles: 15 (0.000008 milliseconds)\n", "\n", "============================================================\n", "Registers:\n", "============================================================\n", "PC: x048E\n", "N: 0 Z: 1 P: 0 \n", "R0: x0000 R1: x0000 R2: x0000 R3: x0000 \n", "R4: x0000 R5: x0000 R6: x0000 R7: x3002 \n" ] } ], "source": [ "%exe" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "That is a little hard to test without have numbers besides zero. Let's store the following into the registers:\n", "\n", "1. R1 gets 1\n", "2. R2 gets 2\n", "3. R3 gets 3\n", "4. R4 gets 4\n", "5. R5 gets 5\n", "5. R6 gets 6\n", "\n", "And then ADD all of the registers together and store the result into R0." ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Assembled! Use %dis or %dump to examine; use %exe to run.\n" ] } ], "source": [ ".ORIG x3000\n", "0001 0010 0010 0001 ;; ADD R1 <- R0 + 1\n", "0001 010 000 1 00010 ;; ADD R2 <- R0 + 2\n", "0001 011 000 1 00011 ;; ADD R3 <- R0 + 3\n", "0001 100 000 1 00100 ;; ADD R4 <- R0 + 4\n", "0001 101 000 1 00101 ;; ADD R5 <- R0 + 5\n", "0001 110 000 1 00110 ;; ADD R6 <- R0 + 6\n", "\n", "1111 0000 00100101 ;; HALT\n", ".END" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "============================================================\n", "Memory dump:\n", "============================================================\n", " x3000: x1221\n", " x3001: x1422\n", " x3002: x1623\n", " x3003: x1824\n", " x3004: x1A25\n", " x3005: x1C26\n", " x3006: xF025\n" ] } ], "source": [ "%dump" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "============================================================\n", "Computation completed\n", "============================================================\n", "Instructions: 7\n", "Cycles: 45 (0.000023 milliseconds)\n", "\n", "============================================================\n", "Registers:\n", "============================================================\n", "PC: x048E\n", "N: 0 Z: 0 P: 1 \n", "R0: x0000 R1: x0001 R2: x0002 R3: x0003 \n", "R4: x0004 R5: x0005 R6: x0006 R7: x3007 \n" ] } ], "source": [ "%exe" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Assembled! Use %dis or %dump to examine; use %exe to run.\n" ] } ], "source": [ ".ORIG x3000\n", "0001 001 000 1 00001 ;; ADD R1 <- R0 + 1\n", "0001 010 000 1 00010 ;; ADD R2 <- R0 + 2\n", "0001 011 000 1 00011 ;; ADD R3 <- R0 + 3\n", "0001 100 000 1 00100 ;; ADD R4 <- R0 + 4\n", "0001 101 000 1 00101 ;; ADD R5 <- R0 + 5\n", "0001 110 000 1 00110 ;; ADD R6 <- R0 + 6\n", "\n", "0001 000 000 0 00 001 ;; ADD R0 <- R0 + R1\n", "0001 000 000 0 00 010 ;; ADD R0 <- R0 + R2\n", "0001 000 000 0 00 011 ;; ADD R0 <- R0 + R3\n", "0001 000 000 0 00 100 ;; ADD R0 <- R0 + R4\n", "0001 000 000 0 00 101 ;; ADD R0 <- R0 + R5\n", "0001 000 000 0 00 110 ;; ADD R0 <- R0 + R6\n", "\n", "1111 0000 00100101 ;; HALT\n", ".END" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "============================================================\n", "Computation completed\n", "============================================================\n", "Instructions: 13\n", "Cycles: 81 (0.000041 milliseconds)\n", "\n", "============================================================\n", "Registers:\n", "============================================================\n", "PC: x048E\n", "N: 0 Z: 0 P: 1 \n", "R0: x0015 R1: x0001 R2: x0002 R3: x0003 \n", "R4: x0004 R5: x0005 R6: x0006 R7: x300D \n" ] } ], "source": [ "%exe" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Program Counter and Debugging the LC-3\n", "\n", "The *program counter*, or PC for short, is a register that keeps track of the line of code that we are executing. It starts out with the value given by .ORIG, and increments by one right before each instruction.\n", "\n", "We can't see the PC increment, unless we using the single-step debugging tools.\n", "\n", "Let's see these in action. Let's use the first program that we wrote above to initialize the registers to values 1 through 6. First we assemble the program:" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Assembled! Use %dis or %dump to examine; use %exe to run.\n" ] } ], "source": [ ".ORIG x3000\n", "0001 001 000 1 00001 ;; ADD R1 <- R0 + 1\n", "0001 010 000 1 00010 ;; ADD R2 <- R0 + 2\n", "0001 011 000 1 00011 ;; ADD R3 <- R0 + 3\n", "0001 100 000 1 00100 ;; ADD R4 <- R0 + 4\n", "0001 101 000 1 00101 ;; ADD R5 <- R0 + 5\n", "0001 110 000 1 00110 ;; ADD R6 <- R0 + 6\n", "\n", "1111 0000 00100101 ;; HALT\n", ".END" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now, instead of %exe executing the code, we will set the PC register manually, and %step through the code:" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "============================================================\n", "Registers:\n", "============================================================\n", "PC: x3000\n", "N: 0 Z: 1 P: 0 \n", "R0: x0000 R1: x0000 R2: x0000 R3: x0000 \n", "R4: x0000 R5: x0000 R6: x0000 R7: x0000 \n" ] } ], "source": [ "%pc x3000" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "============================================================\n", "Stepping... => read, <= write, (Instructions/Cycles):\n", "============================================================\n", " PC <= x3001\n", "(1/6) ADD R1, R0, #1 [1] (x3001*: x1221)\n", " R1 <= x0001\n", " NZP <= (0, 0, 1)\n", "\n", "============================================================\n", "Registers:\n", "============================================================\n", "PC: x3001\n", "N: 0 Z: 0 P: 1 \n", "R0: x0000 R1: x0001 R2: x0000 R3: x0000 \n", "R4: x0000 R5: x0000 R6: x0000 R7: x0000 \n" ] } ], "source": [ "%step" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The first part of the output shows that the PC is getting x3001, and then we execute `ADD R1, R0, #1`. This is a shorthand for our instruction, where #1 stands for immediate mode, value of 1.\n", "\n", "The result is that R1 gets the value x0001. In addition, the N, Z, and P registers get 0, 0, and 1 respectively. The NZP registers are assigned a value based on the last operation:\n", "\n", "* NZP <= (0, 0, 1) ;; if the last operation was a positive number\n", "* NZP <= (0, 1, 0) ;; if the last operation was zero\n", "* NZP <= (1, 0, 0) ;; if the last operation was a negative number\n", "\n", "```\n", "============================================================\n", "Stepping... => read, <= write, (Instructions/Cycles):\n", "============================================================\n", " PC <= x3001\n", "(1/6) ADD R1, R0, #1 [1] (x3001*: x1221)\n", " R1 <= x0001\n", " NZP <= (0, 0, 1)\n", "```\n", "\n", "The last part of the output shows all of the registers:\n", "\n", "```\n", "============================================================\n", "Registers:\n", "============================================================\n", "PC: x3001\n", "N: 0 Z: 0 P: 1 \n", "R0: x0000 R1: x0001 R2: x0000 R3: x0000 \n", "R4: x0000 R5: x0000 R6: x0000 R7: x0000 \n", "```" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "============================================================\n", "Stepping... => read, <= write, (Instructions/Cycles):\n", "============================================================\n", " PC <= x3002\n", "(2/12) ADD R2, R0, #2 [2] (x3002*: x1422)\n", " R2 <= x0002\n", " NZP <= (0, 0, 1)\n", "\n", "============================================================\n", "Registers:\n", "============================================================\n", "PC: x3002\n", "N: 0 Z: 0 P: 1 \n", "R0: x0000 R1: x0001 R2: x0002 R3: x0000 \n", "R4: x0000 R5: x0000 R6: x0000 R7: x0000 \n" ] } ], "source": [ "%step" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Every time we use %step, we increment the PC, and execute the next instruction. You have access to the following metacommands:\n", "\n", "LC3 Interactive Magic Directives: \n", "```\n", " %help - shows this help message\n", " %bp [clear | SUSPENDHEX] - show, clear, or set breakpoints\n", " %cont - continue running\n", " %dump [STARTHEX [STOPHEX]] - list memory in hex\n", " %exe - execute the program\n", " %mem HEXLOCATION HEXVALUE - set memory\n", " %pc HEXVALUE - set PC\n", " %reg REG HEXVALUE - set register REG to HEXVALUE\n", " %regs - show registers\n", " %reset - reset LC3 to start state\n", " %step - increment PC, execute the next instruction\n", "```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Memory Instructions\n", "\n", "The LC-3 contains seven instructions that move information to and from memory: \n", "\n", "1. LD\n", "2. LDR\n", "3. LDI\n", "4. LEA\n", "5. ST\n", "6. STR\n", "7. STI\n", "\n", "The format of the load and store instructions is as follows: \n", "\n", "[15:12] | [11:9] | [8:0]\n", "--------| -----------|---------------------------\n", "OPCODE | DST or SRC | ADDRESS GENERATION BITS" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Data movement instructions require two operands, a source and a destination. The \n", "source is the data to be moved; the destination is the location where it is moved\n", "to. One of these locations is a register, the second is a memory location or an\n", "input/output device. In this chapter the second operand will be assumed to be in memory.\n", "\n", "Bits [11:9] specify one of these operands, the register. If the instruction is\n", "a load, DST refers to the destination register that will contain the value after it is\n", "read from memory (at the completion of the instruction cycle). If the instruction\n", "is a store, SRC refers to the register that contains the value that will be written to\n", "memory.\n", "\n", "Bits [8:0] contain the address generation bits. That is, bits [8:0] encode information\n", "that is used to compute the 16-bit address of the second operand. In the\n", "case of the LC-3's data movement instructions, there are four ways to interpret\n", "bits [8:0]. They are collectively called addressing modes. The opcode specifies\n", "how to interpret bits [8:0]. That is, the LC-3's opcode specifies which addressing\n", "mode should be used to obtain the operand from bits [8:0] of the instruction. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 5.3.1 PC-Relative Mode \n", "\n", "Instruction | [15:12] | [11:9] | [8:0]\n", "------------| --------| -------|---------------------------\n", "LD | 0010 | DST | VVVVVVVVV\n", "ST | 0011 | SRC | VVVVVVVVV\n", "\n", "LD (opcode = 0010) and ST (opcode = 0011) specify the PC-relative addressing\n", "mode. This addressing mode is so named because bits [8:0] of the instruction\n", "specify an offset relative to the PC. The memory address is computed by sign-extending\n", "bits [8:0] to 16 bits, and adding the result to the incremented PC.\n", "\n", "The incremented PC is the contents of the program counter after it has been incremented. If a load, the memory location corresponding to the computed memory address is read, and the result loaded into\n", "the register specified by bits [11:9] of the instruction. \n", "\n", "```\n", "LD DST <= PC+VVVVVVVVV\n", "ST SRC => PC+VVVVVVVVV\n", "```" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Assembled! Use %dis or %dump to examine; use %exe to run.\n" ] } ], "source": [ ".ORIG x3000\n", "0010 000 000000000 ;; LD R0 <= PC+000000000\n", "1111 1111 1111 1111 ;; xFFFF\n", ".END" ] }, { "cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "============================================================\n", "Registers:\n", "============================================================\n", "PC: x3000\n", "N: 0 Z: 1 P: 0 \n", "R0: x0000 R1: x0000 R2: x0000 R3: x0000 \n", "R4: x0000 R5: x0000 R6: x0000 R7: x0000 \n" ] } ], "source": [ "%pc x3000" ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "============================================================\n", "Stepping... => read, <= write, (Instructions/Cycles):\n", "============================================================\n", " PC <= x3001\n", "(1/10) LD R0, x3001 [1] (x3001*: x2000)\n", " Reading memory[x3001] (xffff) =>\n", " R0 <= xFFFF\n", " NZP <= (1, 0, 0)\n", "\n", "============================================================\n", "Registers:\n", "============================================================\n", "PC: x3001\n", "N: 1 Z: 0 P: 0 \n", "R0: xFFFF R1: x0000 R2: x0000 R3: x0000 \n", "R4: x0000 R5: x0000 R6: x0000 R7: x0000 \n" ] } ], "source": [ "%step" ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Assembled! Use %dis or %dump to examine; use %exe to run.\n" ] } ], "source": [ ".ORIG x3000\n", "0010 000 111111111 ;; LD R0 <= PC+-1\n", ".END" ] }, { "cell_type": "code", "execution_count": 26, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "============================================================\n", "Registers:\n", "============================================================\n", "PC: x3000\n", "N: 0 Z: 1 P: 0 \n", "R0: x0000 R1: x0000 R2: x0000 R3: x0000 \n", "R4: x0000 R5: x0000 R6: x0000 R7: x0000 \n" ] } ], "source": [ "%pc x3000" ] }, { "cell_type": "code", "execution_count": 27, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "============================================================\n", "Stepping... => read, <= write, (Instructions/Cycles):\n", "============================================================\n", " PC <= x3001\n", "(1/10) LD R0, x3000 [1] (x3001*: x21FF)\n", " Reading memory[x3000] (x21ff) =>\n", " R0 <= x21FF\n", " NZP <= (0, 0, 1)\n", "\n", "============================================================\n", "Registers:\n", "============================================================\n", "PC: x3001\n", "N: 0 Z: 0 P: 1 \n", "R0: x21FF R1: x0000 R2: x0000 R3: x0000 \n", "R4: x0000 R5: x0000 R6: x0000 R7: x0000 \n" ] } ], "source": [ "%step" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 5.3.2 Indirect Mode\n", "\n", "Instruction | [15:12] | [11:9] | [8:0]\n", "------------| --------| -------|---------------------------\n", "LDI | 1010 | DST | VVVVVVVVV\n", "STI | 1011 | SRC | VVVVVVVVV\n", "\n", "LDI (opcode — 1010) and STI (opcode = 1011) specify the indirect addressing\n", "mode. An address is first formed exactly the same way as with LD and ST.\n", "However, instead of this address **being** the address of the operand to be loaded or\n", "stored, it **contains** the address of the operand to be loaded or stored. Hence the \n", "name indirect. Note that the address of the operand can be anywhere in the computer's\n", "memory, not just within the range provided by bits [8:0] of the instruction\n", "as is the case for LD and ST. The destination register for the LDI and the source\n", "register for STI, like all the other loads and stores, are specified in bits [11:9] of\n", "the instruction. \n", "\n", "```\n", "LDI DST <= M[PC+VVVVVVVVV]\n", "STI SRC => M[PC+VVVVVVVVV]\n", "```" ] }, { "cell_type": "code", "execution_count": 28, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Assembled! Use %dis or %dump to examine; use %exe to run.\n" ] } ], "source": [ ".ORIG x3000\n", "1010 000 000000000\n", "0011 0000 0000 0000\n", ".END" ] }, { "cell_type": "code", "execution_count": 29, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "============================================================\n", "Registers:\n", "============================================================\n", "PC: x3000\n", "N: 0 Z: 1 P: 0 \n", "R0: x0000 R1: x0000 R2: x0000 R3: x0000 \n", "R4: x0000 R5: x0000 R6: x0000 R7: x0000 \n" ] } ], "source": [ "%pc x3000" ] }, { "cell_type": "code", "execution_count": 30, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "============================================================\n", "Stepping... => read, <= write, (Instructions/Cycles):\n", "============================================================\n", " PC <= x3001\n", "(1/12) LDI R0, x3001 [1] (x3001*: xA000)\n", " Reading memory[x3001] (x3000) =>\n", " Reading memory[x3000] (xa000) =>\n", " R0 <= xA000\n", " NZP <= (1, 0, 0)\n", "\n", "============================================================\n", "Registers:\n", "============================================================\n", "PC: x3001\n", "N: 1 Z: 0 P: 0 \n", "R0: xA000 R1: x0000 R2: x0000 R3: x0000 \n", "R4: x0000 R5: x0000 R6: x0000 R7: x0000 \n" ] } ], "source": [ "%step" ] }, { "cell_type": "code", "execution_count": 31, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Assembled! Use %dis or %dump to examine; use %exe to run.\n" ] } ], "source": [ ".ORIG x3000\n", "1011 000 000000000 ;; STI R0 => M[PC+0]\n", "0011 0000 0000 0000\n", ".END" ] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "============================================================\n", "Registers:\n", "============================================================\n", "PC: x3000\n", "N: 0 Z: 1 P: 0 \n", "R0: x0000 R1: x0000 R2: x0000 R3: x0000 \n", "R4: x0000 R5: x0000 R6: x0000 R7: x0000 \n" ] } ], "source": [ "%pc x3000" ] }, { "cell_type": "code", "execution_count": 33, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "============================================================\n", "Stepping... => read, <= write, (Instructions/Cycles):\n", "============================================================\n", " PC <= x3001\n", "(1/12) STI R0, x3001 [1] (x3001*: xB000)\n", " memory[x3000] <= x0000\n", "\n", "============================================================\n", "Registers:\n", "============================================================\n", "PC: x3001\n", "N: 0 Z: 1 P: 0 \n", "R0: x0000 R1: x0000 R2: x0000 R3: x0000 \n", "R4: x0000 R5: x0000 R6: x0000 R7: x0000 \n" ] } ], "source": [ "%step" ] }, { "cell_type": "code", "execution_count": 34, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "============================================================\n", "Memory dump:\n", "============================================================\n", " x3000: x0000\n", " x3001: x3000\n" ] } ], "source": [ "%dump x3000" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 5.3.3 Base+offset Mode\n", "\n", "Instruction | [15:12] | [11:9] | [8:6] | [5:0]\n", "------------| --------| -------|-------|-------------------\n", "LDR | 0110 | DST | BSE | OFFSET\n", "STR | 0111 | SRC | BSE | OFFSET\n", "\n", "LDR (opcode = 0110) and STR (opcode = 0111) specify the Base+offset\n", "addressing mode. The Base+offset mode is so named because the address of the\n", "operand is obtained by adding a sign-extended 6-bit offset to a base register. The\n", "6-bit offset is literally taken from the instruction, bits [5:0]. The base register is\n", "specified by bits [8:6] of the instruction.\n", "\n", "The Base+offset addressing uses the 6-bit value as a 2's complement integer\n", "between —32 and +31. Thus it must first be sign-extended to 16 bits before it is\n", "added to the base register. \n", "\n", "```\n", "LDR DST <= M[BASE + OFFSET]\n", "STR SRC => M[BASE + OFFSET]\n", "```" ] }, { "cell_type": "code", "execution_count": 35, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Assembled! Use %dis or %dump to examine; use %exe to run.\n" ] } ], "source": [ ".ORIG x3000\n", "0110 000 000 000001\n", ".END" ] }, { "cell_type": "code", "execution_count": 36, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "============================================================\n", "Registers:\n", "============================================================\n", "PC: x3000\n", "N: 0 Z: 1 P: 0 \n", "R0: x0000 R1: x0000 R2: x0000 R3: x0000 \n", "R4: x0000 R5: x0000 R6: x0000 R7: x0000 \n" ] } ], "source": [ "%pc x3000" ] }, { "cell_type": "code", "execution_count": 37, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "============================================================\n", "Stepping... => read, <= write, (Instructions/Cycles):\n", "============================================================\n", " PC <= x3001\n", "(1/9) LDR R0, R0, 1 [1] (x3001*: x6001)\n", " Reading memory[x0001] (x0495) =>\n", " R0 <= x0495\n", " NZP <= (0, 0, 1)\n", "\n", "============================================================\n", "Registers:\n", "============================================================\n", "PC: x3001\n", "N: 0 Z: 0 P: 1 \n", "R0: x0495 R1: x0000 R2: x0000 R3: x0000 \n", "R4: x0000 R5: x0000 R6: x0000 R7: x0000 \n" ] } ], "source": [ "%step" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 5.3.4 Immediate Mode\n", "\n", "Instruction | [15:12] | [11:9] | [8:0]\n", "------------| --------| -------|---------------------------\n", "LEA | 1110 | DST | VVVVVVVVV \n", "\n", "The fourth and last addressing mode used by the data movement instructions is\n", "the immediate (or, literal) addressing mode. It is used only with the load effective\n", "address (LEA) instruction. LEA (opcode = 1110) loads the register specified by\n", "bits [11:9] of the instruction with the value formed by adding the incremented\n", "program counter to the sign-extended bits [8:0] of the instruction. The immediate\n", "addressing mode is so named because the operand to be loaded into the destination\n", "register is obtained immediately, that is, without requiring any access of\n", "memory.\n", "\n", "The LEA instruction is useful to initialize a register with an address that\n", "is very close to the address of the instruction doing the initializing.\n", "\n", "```\n", "LEA DST <= PC + VVVVVVVVV\n", "```" ] }, { "cell_type": "code", "execution_count": 38, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Assembled! Use %dis or %dump to examine; use %exe to run.\n" ] } ], "source": [ ".ORIG x3000\n", "1110 000 000000000\n", ".END" ] }, { "cell_type": "code", "execution_count": 39, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "============================================================\n", "Registers:\n", "============================================================\n", "PC: x3000\n", "N: 0 Z: 1 P: 0 \n", "R0: x0000 R1: x0000 R2: x0000 R3: x0000 \n", "R4: x0000 R5: x0000 R6: x0000 R7: x0000 \n" ] } ], "source": [ "%pc x3000" ] }, { "cell_type": "code", "execution_count": 40, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "============================================================\n", "Stepping... => read, <= write, (Instructions/Cycles):\n", "============================================================\n", " PC <= x3001\n", "(1/6) LEA R0, x3001 [1] (x3001*: xE000)\n", " R0 <= x3001\n", " NZP <= (0, 0, 1)\n", "\n", "============================================================\n", "Registers:\n", "============================================================\n", "PC: x3001\n", "N: 0 Z: 0 P: 1 \n", "R0: x3001 R1: x0000 R2: x0000 R3: x0000 \n", "R4: x0000 R5: x0000 R6: x0000 R7: x0000 \n" ] } ], "source": [ "%step" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 5.3.5 An Example\n", "\n", "We conclude our study of addressing modes with a comprehensive example.\n", "Assume the contents of memory locations x30F6 through x30FC are as shown in\n", "Figure 5.10 (and below), and the PC contains x30F6. We will examine the effects of carrying\n", "out the instruction cycle seven consecutive times. " ] }, { "cell_type": "code", "execution_count": 41, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Assembled! Use %dis or %dump to examine; use %exe to run.\n" ] } ], "source": [ ".ORIG x30F6\n", "1110 001 111111101 ;; LEA R1, #-3\n", "0001 010001101110\n", "0011 010111111011\n", "0101 010010100000\n", "0001 010010100101\n", "0111 010001001110\n", "1010 011111110111\n", ".END" ] }, { "cell_type": "code", "execution_count": 42, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "============================================================\n", "Registers:\n", "============================================================\n", "PC: x30F6\n", "N: 0 Z: 1 P: 0 \n", "R0: x0000 R1: x0000 R2: x0000 R3: x0000 \n", "R4: x0000 R5: x0000 R6: x0000 R7: x0000 \n" ] } ], "source": [ "%pc x30F6" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The PC points initially to location x30F6. That is, the content of the PC is\n", "the address x30F6. Therefore, the first instruction to be executed is the one stored\n", "in location x30F6. The opcode of that instruction is 1110, which identifies the\n", "load effective address instruction (LEA). LEA loads the register specified by bits\n", "[11:9] with the address formed by sign-extending bits [8:0] of the instruction\n", "and adding the result to the incremented PC. The 16-bit value obtained by sign-extending\n", "bits [8:0] of the instruction is xFFFD. The incremented PC is x30F7.\n", "Therefore, at the end of execution of the LEA instruction, R1 contains x30F4,\n", "and the PC contains x30F7. " ] }, { "cell_type": "code", "execution_count": 43, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "============================================================\n", "Stepping... => read, <= write, (Instructions/Cycles):\n", "============================================================\n", " PC <= x30F7\n", "(1/6) LEA R1, x30F4 [1] (x30F7*: xE3FD)\n", " R1 <= x30F4\n", " NZP <= (0, 0, 1)\n", "\n", "============================================================\n", "Registers:\n", "============================================================\n", "PC: x30F7\n", "N: 0 Z: 0 P: 1 \n", "R0: x0000 R1: x30F4 R2: x0000 R3: x0000 \n", "R4: x0000 R5: x0000 R6: x0000 R7: x0000 \n" ] } ], "source": [ "%step" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The second instruction to be executed is the one stored in location x30F7.\n", "The opcode 0001 identifies the ADD instruction, which stores the result of adding\n", "the contents of the register specified in bits [8:6] to the sign-extended immediate\n", "in bits [4:0] (since bit [5] is 1) in the register specified by bits [11:9]. Since\n", "the previous instruction loaded x30F4 into R1, and the sign-extended immediate\n", "value is xOOOE, the value to be loaded into R2 is x3102. At the end of execution of\n", "this instruction, R2 contains x3102, and the PC contains x30F8. R1 still contains\n", "x30F4. " ] }, { "cell_type": "code", "execution_count": 44, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "============================================================\n", "Stepping... => read, <= write, (Instructions/Cycles):\n", "============================================================\n", " PC <= x30F8\n", "(2/12) ADD R2, R1, #14 [2] (x30F8*: x146E)\n", " R2 <= x3102\n", " NZP <= (0, 0, 1)\n", "\n", "============================================================\n", "Registers:\n", "============================================================\n", "PC: x30F8\n", "N: 0 Z: 0 P: 1 \n", "R0: x0000 R1: x30F4 R2: x3102 R3: x0000 \n", "R4: x0000 R5: x0000 R6: x0000 R7: x0000 \n" ] } ], "source": [ "%step" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The third instruction to be executed is stored in x30F8. The opcode 0011\n", "specifies the ST instruction, which stores the contents of the register specified by\n", "bits [11:9] of the instruction into the memory location whose address is computed\n", "using the PC-relative addressing mode. That is, the address is computed by adding\n", "the incremented PC to the 16-bit value obtained by sign-extending bits [8:0] of\n", "the instruction. The 16-bit value obtained by sign-extending bits [8:0] of the\n", "instruction is xFFFB. The incremented PC is x30F9. Therefore, at the end of \n", "execution of the ST instruction, memory location x30F4 contains x3102, and the\n", "PC contains x30F9. " ] }, { "cell_type": "code", "execution_count": 45, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "============================================================\n", "Stepping... => read, <= write, (Instructions/Cycles):\n", "============================================================\n", " PC <= x30F9\n", "(3/21) ST R2, x30F4 [3] (x30F9*: x35FB)\n", " memory[x30F4] <= x3102\n", "\n", "============================================================\n", "Registers:\n", "============================================================\n", "PC: x30F9\n", "N: 0 Z: 0 P: 1 \n", "R0: x0000 R1: x30F4 R2: x3102 R3: x0000 \n", "R4: x0000 R5: x0000 R6: x0000 R7: x0000 \n" ] } ], "source": [ "%step" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "At x30F9, we find the opcode 0101, which represents the AND instruction.\n", "After execution, R2 contains the value 0, and the PC contains x30FA. " ] }, { "cell_type": "code", "execution_count": 46, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "============================================================\n", "Stepping... => read, <= write, (Instructions/Cycles):\n", "============================================================\n", " PC <= x30FA\n", "(4/27) AND R2, R2, #0 [4] (x30FA*: x54A0)\n", " R2 <= x0000\n", " NZP <= (0, 1, 0)\n", "\n", "============================================================\n", "Registers:\n", "============================================================\n", "PC: x30FA\n", "N: 0 Z: 1 P: 0 \n", "R0: x0000 R1: x30F4 R2: x0000 R3: x0000 \n", "R4: x0000 R5: x0000 R6: x0000 R7: x0000 \n" ] } ], "source": [ "%step" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "At x30FA, we find the opcode 0001, signifying the ADD instruction. After\n", "execution, R2 contains the value 5, and the PC contains x30FB. " ] }, { "cell_type": "code", "execution_count": 47, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "============================================================\n", "Stepping... => read, <= write, (Instructions/Cycles):\n", "============================================================\n", " PC <= x30FB\n", "(5/33) ADD R2, R2, #5 [5] (x30FB*: x14A5)\n", " R2 <= x0005\n", " NZP <= (0, 0, 1)\n", "\n", "============================================================\n", "Registers:\n", "============================================================\n", "PC: x30FB\n", "N: 0 Z: 0 P: 1 \n", "R0: x0000 R1: x30F4 R2: x0005 R3: x0000 \n", "R4: x0000 R5: x0000 R6: x0000 R7: x0000 \n" ] } ], "source": [ "%step" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "At x30FB, we find the opcode 0111, signifying the STR instruction. The\n", "STR instruction (like the LDR instruction) uses the Base+offset addressing mode.\n", "The memory address is obtained by adding the contents of the register specified\n", "by bits [8:61 (the BASE register) to the sign-extended offset contained in bits\n", "[5:0]. In this case, bits [8:6] specify R1. The contents of R1 are still x30F4.\n", "The 16-bit sign-extended offset is xOOOE. Since x30F4 + xOOOE is x3102, the\n", "memory address is x3102. The STR instruction stores into x3102 the contents of\n", "the register specified by bits [11:9], that is, R2. Recall that the previous instruction\n", "(at x30FA) stored the value 5 into R2. Therefore, at the end of execution\n", "of this instruction, location x3102 contains the value 5, and the PC contains\n", "x30FC. " ] }, { "cell_type": "code", "execution_count": 48, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "============================================================\n", "Stepping... => read, <= write, (Instructions/Cycles):\n", "============================================================\n", " PC <= x30FC\n", "(6/43) STR R2, R1, 14 [6] (x30FC*: x744E)\n", " memory[x3102] <= x0005\n", "\n", "============================================================\n", "Registers:\n", "============================================================\n", "PC: x30FC\n", "N: 0 Z: 0 P: 1 \n", "R0: x0000 R1: x30F4 R2: x0005 R3: x0000 \n", "R4: x0000 R5: x0000 R6: x0000 R7: x0000 \n" ] } ], "source": [ "%step" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "At x30FC, we find the opcode 1010, signifying the LDI instruction. The\n", "LDI instruction (like the STI instruction) uses the indirect addressing mode. The\n", "memory address is obtained by first forming an address as is done in the PC-relative\n", "addressing mode. In this case, the 16-bit value obtained by sign-extending\n", "bits [8:0] of the instruction is xFFF7. The incremented PC is x30FD. Their sum\n", "is x30F4, which is the address of the operand address. Memory location x30F4\n", "contains x3102. Therefore, x3102 is the operand address. The LDI instruction\n", "loads the value found at this address (in this case 5) into the register identified\n", "by bits [11:9] of the instruction (in this case R3). At the end of execution of this\n", "instruction, R3 contains the value 5 and the PC contains x30FD. " ] }, { "cell_type": "code", "execution_count": 49, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "============================================================\n", "Stepping... => read, <= write, (Instructions/Cycles):\n", "============================================================\n", " PC <= x30FD\n", "(7/55) LDI R3, x30F4 [7] (x30FD*: xA7F7)\n", " Reading memory[x30f4] (x3102) =>\n", " Reading memory[x3102] (x0005) =>\n", " R3 <= x0005\n", " NZP <= (0, 0, 1)\n", "\n", "============================================================\n", "Registers:\n", "============================================================\n", "PC: x30FD\n", "N: 0 Z: 0 P: 1 \n", "R0: x0000 R1: x30F4 R2: x0005 R3: x0005 \n", "R4: x0000 R5: x0000 R6: x0000 R7: x0000 \n" ] } ], "source": [ "%step" ] } ], "metadata": { "kernelspec": { "display_name": "Calysto LC3", "language": "asm", "name": "calysto_lc3" }, "language_info": { "file_extension": ".asm", "mimetype": "text/x-gas", "name": "gas" } }, "nbformat": 4, "nbformat_minor": 2 }